package iterator;

import java.io.IOException;

import iterator.exceptions.TupleUtilsException;
import iterator.exceptions.UnknowAttrType;
import global.AttrType;
import global.TupleOrder;

public class pnodeSplayPQ extends pnodePQ {

	protected pnodeSplayNode root;

	/**
	 * sets default values
	 */
	public pnodeSplayPQ() {
		root = null;
		count = 0;
		fld_no = 0;
		fld_type = new AttrType(AttrType.attrInteger);
		sort_order = new TupleOrder(TupleOrder.Ascending);
	}

	public int size() {
		return count;
	}

	/**
	 * constructor
	 * 
	 * @param fieldNo
	 * @param fieldType
	 * @param order
	 */
	public pnodeSplayPQ(int fieldNo, AttrType fieldType, TupleOrder order) {
		root = null;
		count = 0;
		fld_no   = fieldNo;
		fld_type = fieldType;
		sort_order = order;
	}

	private pnodeSplayNode getMaxValue(pnodeSplayNode curr) {
		pnodeSplayNode node;
		if (curr.rt != null) {
			node = getMaxValue(curr.rt);
		} else {
			return curr;
		}
		return null;
	}

	private pnodeSplayNode getMinValue(pnodeSplayNode curr) {
		pnodeSplayNode node;
		if (curr.lt != null) {
			node = getMaxValue(curr.lt);
		} else {
			return curr;
		}
		return null;
	}

	@Override
	pnode deq() {
		if (root == null) {
			return null;
		}
		count--;
		pnodeSplayNode newRoot = root;
		pnodeSplayNode left = root.lt;
		if (left == null) {
			// no items in the left ,, return the root
			if ((root = newRoot.rt) != null)
				root.par = null;
			return newRoot.item;
		} else {
			while (true) {
				pnodeSplayNode leftl = left.lt;
				if (leftl == null) {
					if ((newRoot.lt = left.rt) != null) {
						newRoot.lt.par = newRoot;
					}
					return left.item;
				} else {
					pnodeSplayNode leftll = leftl.lt;
					if (leftll == null) {
						if ((left.lt = leftl.rt) != null) {
							left.lt.par = left;
						}
						return leftl.item;
					} else {
						newRoot.lt = leftl; leftl.par = newRoot;
						if ((left.lt = leftl.rt) != null) left.lt.par = left;
						leftl.rt = left; left.par = leftl;
						newRoot = leftl;
						left = leftll;
					}
				}

			} // end while true
		}// end else
			// TODO Auto-generated method stub

	}

	@Override
	void enq(pnode item) throws UnknowAttrType, TupleUtilsException, IOException {
		count++;
		pnodeSplayNode newNode = new pnodeSplayNode(item);
		pnodeSplayNode newRoot = root;
		if (root == null) {
			root = new pnodeSplayNode(item);
			return;
		}
		int comp = pnodeCMP(item, newRoot.item);
		pnodeSplayNode leftDummy = pnodeSplayNode.dummy;
		pnodeSplayNode rightDummy = pnodeSplayNode.dummy;
		boolean done = false;
		while (!done) {
			// always insert not needed value on the right i.e value>root and
			// Asc.or value<root and desc.
			if ((sort_order.tupleOrder == TupleOrder.Ascending && comp >= 0)
					|| (sort_order.tupleOrder == TupleOrder.Descending && comp <= 0)) {
				pnodeSplayNode right = newRoot.rt;
				if (right == null) {
					// stopping condition ..here right is null and in case of
					// asc it's the least value
					// in case of desc. it's the largest value
					right = newNode;
					done = true;
					comp = 0;
				} else {
					comp = pnodeCMP(item, right.item);
				}
				if ((sort_order.tupleOrder == TupleOrder.Ascending && comp <= 0)
						|| (sort_order.tupleOrder == TupleOrder.Descending && comp >= 0)) {
					// must continue the loop
					// keeping the previous root
					leftDummy.rt = newRoot;
					newRoot.par = leftDummy;
					leftDummy = newRoot;
					// continue the loop
					newRoot = right;
				} else {
					// the condition has been satisified
					pnodeSplayNode rightr = right.rt;
					if (rightr == null) {
						rightr = newNode;
						comp = 0;
						done = true;
					} else {
						comp = pnodeCMP(item, rightr.item);
					}
					if ((newRoot.rt = right.lt) != null) {
						newRoot.rt.par = newRoot;
					}
					right.lt = newRoot;
					newRoot.par = right;
					leftDummy.rt = right;
					right.par = leftDummy;
					leftDummy = right;
					newRoot = rightr;
				}
			}// end comp>=0
			else {
				// the same as previous but in the left branch
				pnodeSplayNode left = newRoot.lt;
				if (left == null) {
					left = newNode;
					comp = 0;
					done = true;
				} else
					comp = pnodeCMP(item, left.item);

				if ((sort_order.tupleOrder == TupleOrder.Ascending && comp >= 0)
						|| (sort_order.tupleOrder == TupleOrder.Descending && comp <= 0)) {
					rightDummy.lt = newRoot;
					newRoot.par = rightDummy;
					rightDummy = newRoot;
					newRoot = left;
				} else {
					pnodeSplayNode leftl = left.lt;
					if (leftl == null) {
						leftl = newNode;
						comp = 0;
						done = true;
					} else
						comp = pnodeCMP(item, leftl.item);

					if ((newRoot.lt = left.rt) != null)
						newRoot.lt.par = newRoot;
					left.rt = newRoot;
					newRoot.par = left;
					rightDummy.lt = left;
					left.par = rightDummy;
					rightDummy = left;
					newRoot = leftl;
				}
			}// end else
		}// end while
		if ((rightDummy.lt = newRoot.rt) != null)
			rightDummy.lt.par = rightDummy;
		if ((leftDummy.rt = newRoot.lt) != null)
			leftDummy.rt.par = leftDummy;
		if ((newRoot.lt = pnodeSplayNode.dummy.rt) != null)
			newRoot.lt.par = newRoot;
		if ((newRoot.rt = pnodeSplayNode.dummy.lt) != null)
			newRoot.rt.par = newRoot;
		newRoot.par = null;
		root = newRoot;

	}
	// @Override
	// void enq(pnode item) {
	// count++;
	// if(root == null){
	// root = new pnodeSplayNode(item);
	// return;
	// }
	// pnodeSplayNode m_root=root;
	// pnodeSplayNode curr = new pnodeSplayNode(item);
	// while(m_root!=null){
	// //check if data is duplicated
	// int comp = pnodeCMP(item, m_root.item);
	// if(comp==0){
	// return ; //the same
	// }else if(comp<0){
	// //insert left
	// if(m_root.lt==null){
	// m_root.lt = curr;
	// curr.par = m_root;
	// root = m_root;
	// return;
	// }else{
	// m_root = m_root.lt;
	// }
	// }else{
	// //insert right
	// if(m_root.rt==null){
	// m_root.rt = curr;
	// curr.par = m_root;
	// root = m_root;
	// return;
	// }else{
	// m_root = m_root.rt;
	// }
	// }
	// }
	//
	// }
	// from wikipedia :D
	// public void insert(int data) {
	// if (m_root == null) {
	// m_root = new TreeNode(data, null, null);
	// return;
	// }
	// Node root = m_root;
	// while (root != null) {
	// // Not the same value twice
	// if (data == root.getData()) {
	// return;
	// } else if (data < root.getData()) {
	// // insert left
	// if (root.getLeft() == null) {
	// root.setLeft(new TreeNode(data, null, null));
	// return;
	// } else {
	// root = root.getLeft();
	// }
	// } else {
	// // insert right
	// if (root.getRight() == null) {
	// root.setRight(new TreeNode(data, null, null));
	// return;
	// } else {
	// root = root.getRight();
	// }
	// }
	// }
	// }

}
